An error correcting decoder is typically implemented, e.g., in a network system, to reduce communication errors. One type of an error correcting decoder is an iterative error correcting decoder. Iterative error correcting decoders typically use a large-scale parallel network of nodes performing soft probability calculation. These nodes exchange probability information of a received data block among one another. After a certain number of iterations within an iterative decoder structure, individual noisy information in a data block (or word) is transformed into an estimate of the word as a whole. Examples of iterative decoders are the low density parity check (LDPC) decoders, Hamming decoders, Turbo decoders, and the like.
The structure of an iterative error correcting decoder can be represented graphically by a factor graph. A factor graph consists of nodes and edges, where the edges represent wire connections between the nodes, and a node represents a function of its inputs. For example, in a low density parity check (LDPC) factor graph, there are two types of nodes representing two distinct functions—i.e., “equality constraint” nodes and “parity check” nodes. According to the IEEE 802.3ae (10 GBASE-T) standard, the proposed LDPC decoder consists of (2048) equality constraint nodes and (384) parity check nodes. Each equality constraint node has (6) bidirectional connections to corresponding parity constraint nodes and each parity check node has a total of (32) bidirectional connections to corresponding equality constraint nodes. This results in a factor graph with network matrix of (12,228) connections. The probabilities associated with received bit values iterate between these two node functions to finally resolve the most probable value of each data bit.
LDPC code is specified by a parity check matrix (which is commonly referred to as an H matrix) having a very few number of “ones” per row. An example H matrix 100 is shown in FIG. 1. The length of each codeword is equal to the number of columns in the H matrix 100. In one example, each codeword is created such that the parity of each set of bits corresponding to the “ones” in a row is even. The number of rows corresponds to the number of parity checks that the codeword must satisfy. Therefore, if all errors in a received codeword are corrected by the decoder, all parity checks must be satisfied for the output codeword.
Each received data bit from a channel has a probability value (e.g., a continuous analog value or a multi-bit resolution value after an analog-to-digital conversion) associated with the data bit. The associated data value identifies the probability of the bit being “1” or “0”. LDPC decoding is based on soft decoding of probabilities—i.e., probability values of bits are received in a pre-coded codeword, which codeword goes through multiple iterations of calculations based on the H matrix to arrive at enhanced probabilities. After a last iteration, a slicer determines if the original bit value was a “1” or a “0” based on a final enhanced probability associated with the bit. The two node functions in LDPC decoding—equality constraint nodes and parity check nodes—perform probability calculations as described below.
A given equality constraint node receives an initial intrinsic probability of each bit of a codeword together with a probability correction value from N parity check nodes (where N is the number of 1's in each column of the H matrix). The equality constraint node multiplies all the probabilities together and at each of the N connections, a new output probability value is determined, in which the new probability value is the product of all of the probabilities divided by the probability of that connection. In a digital domain, to replace more complex multipliers with simpler adders, the probability ratios of a bit (e.g., P1/P0) are converted to a logarithmic domain—i.e., log likelihood ratios (LLR)—and the LLR values are added.
A parity check node receives the output of M equality constraint nodes (where M is the number of 1's in each row of the H matrix), and performs a probability sum-product function. For example, if a parity check node connects to three equality constraint nodes A, B, C, then the output at connection A is given by:PB0PC1+PB1PC0  eq. (1)and the output at connection B is given by:PA0PC1+PA1PC0  eq. (2)and so on. Again, to avoid the use of complex multipliers, conventional techniques include use of a hyperbolic tangent that directly operates on LLR values. Another technique for performing a parity check is through use of the min-sum function. Although the min-sum function is significantly less implementation intensive compared to the sum-product function, the min-sum function generally suffers from lower decoding gain. However, a modification to the min-sum algorithm has been proposed—i.e., the “min-sum with correction” algorithm—that results in a decoder having a similar decoding gain to an implementation of the sum-product function. The “min-sum with correction” algorithm is described in an article entitled “Reduced complexity decoding of LDPC codes,” by J. Cheng, et al., IEEE Transactions on Communication, vol. 53, no. 8, pp. 1288-1299, August 2005, which is incorporated by reference herein.
An important feature of one implementation of an iterative decoder is the number of iterations that the iterative decoder can perform on an input codeword in a given amount of time as it relates to the bit error rate (BER) of the iterative decoder. A higher number of iterations results in a better BER performance of an iterative decoder. Therefore, to maximize the performance of a single iterative decoder, it is generally preferred to have a given iterative decoder perform a higher number of iterations in a certain time interval—i.e., to go through a certain number of equality constraint and parity check nodes per unit time (which determines the BER performance of the iterative decoder). Another factor that affects the performance of a digital decoder is the resolution of probability messages at the inputs and between equality constraint nodes and parity check nodes. A higher resolution can potentially result in better performance of the decoder as probability calculations are performed more accurately and with a smaller error.
Accordingly, there is a trade off between the number of iterations an iterative decoder can perform in a time interval of each data codeword versus the power and complexity of the iterative decoder. In a digital iterative decoder, one can increase the clock frequency, increase the gate sizes, add more flip-flops between logic stages, adopt different implementation architectures, and/or run at higher supply voltage in order to get more iterations per codeword at cost of more power.